<?php
/*
	插入排序 ：
	每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
	//在这里我用了后扫描和前扫描的方法
*/
	//从后往前比较
	$arr=array(1,43,54,62,21,66,32,78,36,76,39);  
	function insertSortH($arr) {
	    $len=count($arr); 
	    for($i=1; $i<$len; $i++) {
	        $tmp = $arr[$i];
	        //内层循环控制，比较并插入
	        for($j=$i-1;$j>=0;$j--) {
	            if($tmp < $arr[$j]) {
	                //发现插入的元素要小，交换位置，将后边的元素与前面的元素互换
	                $arr[$j+1] = $arr[$j];
	                $arr[$j] = $tmp;
	            } else {
	                //如果碰到不需要移动的元素，由于是已经排序好是数组，则前面的就不需要再次比较了。
	                break;
	            }
	        }
	    }
	    return $arr;
	}
	//从前往后比较
    function insertSortQ($a){
        $len = count($a);
        for($i = 1;$i < $len;$i++){
            //内层
            $comparePa = $a[$i];
            for ($j=0; $j < $i; $j++) {
                if($comparePa < $a[$j]){
                    $temp = $a[$j];
                    $a[$j] = $comparePa;
                    $a[$i] = $temp;
                    $comparePa = $temp;
                }
            }
        }
        return $a;
    }

	print_r(insertSortH($arr));
	print_r(insertSortQ($arr));


